﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Reflection.Metadata;
using System.Text;
using System.Threading.Tasks;

namespace ZuoAlgorithms.Class018;

// 不用递归，用迭代的方式实现二叉树的三序遍历
public class BinaryTreeTraversalIteration
{
    public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int v)
        {
            this.val = v;
        }
    }

    // 先序打印所有节点，非递归点
    public void PreOrder(TreeNode head)
    {
        if (head != null)
        {
            Stack<TreeNode> stk = new Stack<TreeNode>();
            stk.Push(head);
            while (stk.Count != 0)
            {
                head = stk.Pop();
                Console.WriteLine(head.val + " ");
                if (head.right != null)
                {
                    stk.Push(head.right);
                }
                if (head.left != null)
                {
                    stk.Push(head.left);
                }
            }
            Console.WriteLine();
        }

    }

    // 中序打印所有节点，非递归版
    public void InOrder(TreeNode head)
    {
        if (head != null)
        {
            Stack<TreeNode> stk = new Stack<TreeNode>();
            while (stk.Count != 0 || head != null)
            {
                if (head != null)
                {
                    stk.Push(head);
                    head = head.left;
                }
                else
                {
                    head = stk.Pop();
                    Console.WriteLine(head.val + " ");
                    head = head.right;
                }
            }
            Console.WriteLine();
        }

    }

    // 后序打印所有节点，非递归版
    // 这是用两个栈的方法
    public void PosOrderTwoStacks(TreeNode head)
    {
        if (head != null)
        {
            Stack<TreeNode> stk = new Stack<TreeNode>();
            Stack<TreeNode> collect = new Stack<TreeNode>();
            stk.Push(head);
            while (stk.Count != 0)
            {
                head = stk.Pop();
                collect.Push(head);
                if (head.left != null)
                {
                    stk.Push(head.left);
                }
                if (head.right != null)
                {
                    stk.Push(head.right);
                }
            }
            while (collect.Count != 0)
            {
                Console.WriteLine(collect.Pop().val + " ");
            }
            Console.WriteLine();
        }
    }

    // 后序打印所有节点，非递归版
    // 这是用一个栈的方法
    public void PosOrderOneStack(TreeNode head)
    {
        if (head != null)
        {
            Stack<TreeNode> stk = new Stack<TreeNode>();
            stk.Push(head);
            // 如果始终没有打印过节点，h就一直是头节点
            // 一旦打印过节点，h就变成打印节点
            // 之后h的含义 : 上一次打印的节点
            while (stk.Count != 0)
            {
                TreeNode cur = stk.Peek();
                if (cur.left != null && head != cur.left && head != cur.right)
                {
                    // 有左树且左树没处理过
                    stk.Push(cur.left);
                }
                else if (cur.right != null && head != cur.right)
                {
                    // 有右树且右树没处理过
                    stk.Push(cur.right);
                }
                else
                {
                    // 左树、右树 没有 或者 都处理过了
                    Console.WriteLine(cur.val + " ");
                    head = stk.Pop();
                }
            }
            Console.WriteLine();
        }
    }


}